1. Field of the Invention
The present invention relates in general to electromagnetic scattering calculations. More specifically, it relates to an efficient method for storing quantities used by the Fast Multipole Method (FMM) to perform field calculations.
2. Description of Related Art
When electromagnetic energy is incident on a conductive material, surface currents are induced on the object being irradiated. These surface currents radiate electromagnetic energy that can be detected and measured. This is the basic principle by which radar detection systems work.
Referring to FIG. 1, an object, referred to as a scatterer S, is shown. The scatterer S represents any three-dimensional conductive object that can be irradiated with plane waves of electromagnetic energy. P.sub.1 to P.sub.N represent N different plane waves that irradiate the scatterer. Q.sub.1 to Q.sub.N represent radiated energy from the scatterer resulting from the surface currents induced on the object by the irradiating plane waves. This energy from the scatterer S is also known as scatter or scattering amplitude. The scattering amplitude is the ratio of the reflected (or scattered) energy to the incident energy. For many applications it is necessary to irradiate the scatterer S from many different angles on many different sides, often referred to as look angles or right hand sides, when measuring scattering amplitude.
Scattering amplitude measurements are useful in a variety of applications such as circuit and antenna modeling. However, the most common use of electromagnetic scattering is in radar systems. Radar systems rely on the principle that all conductive objects re-radiate incident electromagnetic energy in patterns that are dependent on that object's particular size, shape and other physical characteristics. In other words, all objects possess "electromagnetic fingerprints." Once the scatter information of an object has been thoroughly determined in all directions, this information can be used to identify that object. Many defense-related aircraft are designed to produce as little scatter as possible in order to minimize the likelihood of the aircraft being detected by an enemy radar system.
The electromagnetic scatter of an object can be determined by empirical methods or by simulation/computation methods. Empirical methods can be costly and time consuming to implement. For example, making scatter measurements is time consuming because the scatterer must be characterized in both the horizontal and the vertical planes. In other words, the scattering characteristics of the scatterer must be known from any point in space surrounding the object. Additionally, empirical scatter measurements are typically made from an actual scatterer by placing the scatterer on a table that rotates during the measurements. When the scatterer is a large and/or expensive object such as an aircraft, the expense associated with conducting such measurements can be readily appreciated.
Computational methods use mathematical models to determine the scattering characteristics of a given object, thus eliminating the need to actually construct and test the object. In general, computational methods resolve an irradiating source into surface currents on the scatterer. Once the surface currents are known, the re-radiated field from the scatterer can be computed. Conventional computational methods break the scatterer into N small cells (unknowns) for computational analysis. A higher number of unknowns results in a more precise simulation, but also requires increased computational power.
FIG. 2 is a two-dimensional cross section of a three-dimensional scatterer S broken into N different cells. The cells are denoted by numbers such as n=1, n=2, etc. Accordingly, each cell shown as a square in FIG. 2 is actually a cube having a depth in the y direction equal to the cell height in the z direction and the cell width in the x direction. Additionally, not shown in FIG. 2 are cells located behind the cells shown. For example, located in the y direction behind cell n=1 is a stack of cells that cannot be shown in the two-dimensional drawing in FIG. 2.
One method of calculating the characteristics of a scatterer is the Fast Multipole Method (FMM). FMM segments a scatterer into a number of cells as shown in FIG. 2. However, preferably the FMM groups the N cells in a hierarchical fashion. That is, the smallest groups of cells in FIG. 2 represent level 0 of a hierarchical structure and levels 1 and 2 represent higher levels in the hierarchical structure. For example as shown in FIG. 3, eight level 0 cells are grouped into a single level 1 group. Similarly, eight level 1 groups, or sixty-four level 0 cells, may be grouped into a single level 2 group. With reference to FIG. 2, hierarchical grouping results in cells n=1 to n=16 being grouped together into a single level 2 group. This cubic grouping structure is not limited to three group levels. Rather, the number of levels is limited by the size of the level 0 cells and the physical size of the scatter under analysis.
Collecting the scatterer cells into groups allows for the decomposition of the impedance matrix Z into sparse components Z', V, and T such that Equation 1 holds. EQU Z.apprxeq.Z'+VTV.dagger. (1)
Equation 1 represents the impedance for a single level of groups. Multiple level groupings use recursive decompositions. However, even though recursive decomposition is used in multiple level systems, the translation operators for the interactions maintain the same form. Fields due to currents within a group m are tabulated at K points, or far-field directions, on a unit sphere. In Equation 1, T is the translation operator, which serves to translate tabulated fields between groups that are far from one another. At a given group, the translated fields from all far away groups are summed and used to compute the interactions on the current elements within the given group. For interactions due to groups nearby a given group, a sparse portion Z' of the regular impedance matrix is used. The variables used in Equation 1 can all be calculated from Equations 2-4. ##EQU1##
In Equation 2, the number inserted for the variable L depends on the desired accuracy, k is the unit vector in the kth far field direction, X .sub.mm' is the unit vector from the center of the group m to group m' and h.sub.l.sup.(1), P.sub.l, and k.sub.o are the Hankel function, the Legendre polynomial, and the wave number, respectively.
V.sub.nk =.sub.e.sup.ik.multidot.(xn-Xm) (3) EQU Z'.sub.nn' =G(r) (4)
In Equations 3 and 4, x.sub.n is the location of the unknown n, X.sub.m is the center of the group m that contains n, r=.vertline.x.sub.n -x.sub.n'.vertline. for unknowns n, n' in nearby groups, and G(r) is the Green function.
Additional details regarding FMM can be found in the following documents: R. F. Harrington, Chapter 1 of Field Computation By Moment Methods, MacMillian, New York, N.Y., 1968; R. Coifman, V. Rokhlin, and S. Wandzura, The Fast Multipole Method: A Pedestrian Prescription, IEEE Antennas and Propagation Society Magazine, June 1993, pages 7-12; V. Rokhlin, Rapid Solution Of Integral Equations Of Classical Potential Theory, J. Comp. Phys., 60 (1985), pages 187-207; M. A. Stalzer, Parallelizing The Fast Multipole Method For The Helmholtz Equation, Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, February 1995, pages 325-330; and M. A. Stalzer, A Parallel Fast Multipole Method For The Helmholtz Equation, Parallel Processing Letter, 5 (1995), pages 263-274. The entire disclosure of each of the above-listed documents is incorporated herein by reference.
For large simulations the storage of the translation operators, as calculated by Equation 2, is cumbersome. For example, simulations having roughly 100,000 unknowns requires approximately 190 Megabytes (MB) of storage space to store the translation operators in the form T.sub.mm'k. The problem of storing such extensive volumes of data can be readily appreciated.